class Solution(object):
    def __init__(self):
        self.cache = {}

    def prepare(self, pattern):
        op = ''
        while op != pattern:
            op = pattern
            pattern = pattern.replace('**', '*')
        return op

    def isMatch(self, s, p):
        np = self.prepare(p)
        self.s = s
        self.p = np
        return self._isMatch()
    
    def _isMatch(self, si=0, pi=0):
        if (si, pi) in self.cache:
            return self.cache[(si, pi)]
        pp = self.p[pi:].strip('*')
        if si == len(self.s) and len(pp) == 0:
            return True
        if pi == len(self.p):  # 且s没有匹配完
            return False
        if si == len(self.s) and len(pp) != 0:
            return False
        ns, np = self.s[si], self.p[pi]
        if (np == '?'):
            self.cache[(si, pi)] = self._isMatch(si+1, pi+1)
            return self.cache[(si, pi)]
        if (np == '*'):
            self.cache[(si, pi)] = self._isMatch(si, pi+1) or self._isMatch(si+1, pi)
            return self.cache[(si, pi)]
        if (np == ns):
            self.cache[(si, pi)] = self._isMatch(si+1, pi+1)
            return self.cache[(si, pi)]
        self.cache[(si, pi)] = False
        return self.cache[(si, pi)]


if __name__ == "__main__":
    # Offical test
    assert Solution().isMatch('aa', 'a') == False
    assert Solution().isMatch('aa', '*') == True
    assert Solution().isMatch('cb', '?a') == False
    assert Solution().isMatch("adceb", '*a*b') == True
    assert Solution().isMatch('acdcb', "a*c?b") == False
    # User defined test
    assert Solution().isMatch('abc', 'abc') == True
    assert Solution().isMatch('abce', 'abcd') == False
    assert Solution().isMatch('abbd', 'ab?d') == True
    assert Solution().isMatch('abdes', 'ab??s') == True
    assert Solution().isMatch('abdes', 'ab*?s') == True
    assert Solution().isMatch('abs', 'ab*?s') == False
    assert Solution().isMatch('abcs', 'ab*?*s') == True
    # failed test case
    assert Solution().isMatch('', '******') == True
    assert Solution().isMatch('b', "*?*?*") == False
    assert Solution().isMatch('a', "*?*") == True
    assert Solution().isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba", "*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*") == True
